struct Code;
struct Entry;

int  parse  (char* input);
bool getBit (const void* input, unsigned int bit);
void setBit (void* input, unsigned int bit, bool flag);

int  getFrequency          (Node<Entry>* array[256], const char* text);
int  shrinkImaginaryEntrys (Node<Entry>* array[256]);

void fillLetterMap (std::map<char, Code>* map, Node<Entry>* tree, bool start,
                    char base[4], int size, bool right);

Node<Entry>* buildHuffmanTree (const char* text);

void decode (Node<Entry>* tree, const char* text, char* output, int limit);
int  code   (Node<Entry>* tree, const char* text, char* output, int limit);

void debugPrintTree (Node<Entry>* node, char legacy[10], int size, bool right);

/** struct Entry
 *
 * 
 * This structure represents letter and it's frequency
 *
 */
struct Entry
{
    int  frequency;
    char letter;
};

/** struct Code
 *
 * 
 * This structure represents coded letter. It desribes how many bits in the
 * code and the code itself.
 *
 */
struct Code
{
    int bits;
    char code[4];
};

/** bool getBit (const void* input, unsigned int bit)
 *
 * This function retreives bit from array
 *
 * @param const void* input - array with bytes
 * @param unsigned int bit - indexo of a bit in array
 * 
 * @return - state of the bit
 *
 */
bool getBit (const void* input, unsigned int bit)
{
    unsigned char* byte = (unsigned char*) input;

    byte += bit / 8;
    bit = bit % 8;

    unsigned char compareByte = 0x80 >> bit;

    return compareByte & *byte;
}

/** void setBit (void* input, unsigned int bit, bool flag)
 *
 * This function sets bit in array.
 *
 * @param void* input - array
 * @param unsigned int bit - indexo of the bit
 * @param bool flag - state to set bit to.
 * 
 *
 */
void setBit (void* input, unsigned int bit, bool flag)
{
    unsigned char* byte = (unsigned char*) input;

    byte += bit / 8;
    bit = bit % 8;

    if ( flag )
    {
        unsigned char setByte = 0x80 >> bit;
        *byte = setByte | *byte;
    }
    else
    {
        unsigned char setByte = 0xFF ^ ( 0x80 >> bit );
        *byte = setByte & *byte;
    }
}


/** void getFrequency (Node<Entry>* array[256], const char* text)
 *
 * This functions gets frequencies of every ascii code from the text and
 * shrinks it so only non zero frequency letters last.
 *
 * @param Node<Entry>* array[256] - array with nodes that contain Entries to
 * be filled with information
 * @param const char* text - text to analyse
 *
 * @return - int number of non-zero frequent codes
 * 
 */
int getFrequency (Node<Entry>* array[256], const char* text)
{
    if ( !text )
        return -1;

    try
    {
        for (int i = 0; i < 256; i++)
            array[i] = new Node<Entry>;
    }
    catch (std::bad_alloc)
    {
        return -1;
    }

    for (int i = 0; i < 256; i++)
    {
        if ( !array[i] )
            return -1;
        if ( ! array[i]->ok() )
            return -1;
        array[i]->getValue()->frequency = 0;
        array[i]->getValue()->letter = i;
    }

    text--;
    while ( *++text )
        array[*text]->getValue()->frequency += 1;

    return shrinkImaginaryEntrys (array);
}

/** int shrinkImaginaryEntrys (Node<Entry>* array[256])
 *
 * This function deletes ascii codes with zero frequency from array of nodes
 *
 * @param Node<Entry>* array[256] - arrray with nodes
 *
 * @return int - number of nodes left
 * 
 *
 */
int shrinkImaginaryEntrys (Node<Entry>* array[256])
{
    int write = 0;
    for (int i = 0; i < 256; i++)
    {
        if ( array[i]->getValue()->frequency > 0 )
        {
            array[write] = array[i];
            write++;
        }
        else
        {
            delete array[i];
            array[i] = nullptr;
        }
    }
    return write;
}

/** void getLowest (int& lowest, int preLowest&, Node<Entry>* frequency[256])
 *
 * This function finds lowest and preLowest letter by frequency.
 * 
 * @param int& lowest - reference to a varible to put lowest frequency index
 * @param int& preLowest - ref to a varible to put preLowest frequency index
 * @param Node<Entry>* frequency[256] - array with frequencies
 * @param int size - amount of non zero frequent elements in array
 *
 */
void getLowest (int& lowest, int& preLowest, Node<Entry>* frequency[256],
                int size)
{
    for (int j = 0; j < size; j++)
    {
        if ( frequency[j] )
        {
            if ( lowest < 0 )
            {
                lowest = j;
                continue;
            }
            if ( preLowest < 0 )
            {
                if ( frequency[lowest]->getValue()->frequency <
                     frequency[  j   ]->getValue()->frequency )
                {
                    preLowest = j;
                }
                else
                {
                   preLowest = lowest;
                   lowest = j;
                }
                continue;
            }
            if ( frequency[preLowest]->getValue()->frequency >
                 frequency[    j    ]->getValue()->frequency )
            { 
                if ( frequency[lowest]->getValue()->frequency <
                     frequency[  j   ]->getValue()->frequency )
                {
                    preLowest = j;
                }
                else
                {
                   preLowest = lowest;
                   lowest = j;
                }
                continue;
            }
        }
    }
}

/** Node<Entry>* buildHuffmanTree (const char* text)
 *
 * This function builds Huffman tree based on given text
 *
 * @param const char* text - text to build Huffman tree from
 *
 * @return Node<Entry>* - the root node of Huffman tree
 *
 */
Node<Entry>* buildHuffmanTree (const char* text)
{
    Node<Entry>* frequency[256] = {};
    int size = getFrequency (frequency, text);
    if ( size == -1 )
        return nullptr;
    if ( size == 1 )
        return frequency[0];
    for (int i = 1; i < size; i++)
    {
        int lowest = -1;
        int preLowest = -1;
        getLowest (lowest, preLowest, frequency, size);

        Node<Entry>* bridge = new Node<Entry>;

        Entry* value = bridge->getValue();
        value->letter = 0;

        bridge->attatchToRight (frequency[lowest]);
        bridge->attatchToLeft  (frequency[preLowest]);

        frequency[lowest] = nullptr;
        frequency[preLowest] = bridge;
    }
    for (int i = 0; i < size; i++)
        if ( frequency[i] )
            return frequency[i];
    return nullptr;
}

/** void fillLetterMap (std::map<char, Code>* map, Node<Entry>* tree, bool start,
 *                      char base[4], int size, bool right)
 *
 * This function fills map with Codes to make access to codes faster. This
 * functuion is recursive.
 *
 * @param std::map<char, Code>* map - map to fill
 * @param Node<Entry>* tree - the root node of Huffman tree to get Codes from
 * @param bool start - Is this the first call of this function.
 * @param char base[4] - any array of 4 bytes
 * @param int size - the iteration of recursion. When first called must be zero.
 * @param bool right - is this function called for right leaf. When first call
 * must be true
 *
 */
void fillLetterMap (std::map<char, Code>* map, Node<Entry>* tree, bool start,
                    char base[4], int size, bool right)
{
    if ( start )
    {
        if ( tree->getLeftChild () )
            fillLetterMap (map, tree->getLeftChild(), false, base, 0, false);
        if ( tree->getRightChild () )
            fillLetterMap (map, tree->getRightChild(), false, base, 0, true);
    }
    setBit (base, size, right);
    if ( tree->getValue()->letter != 0 )
    {
        Code code = {};
        code.bits = size + 1;
        memcpy (code.code, base, 4);
        std::pair<char, Code> pair = {tree->getValue()->letter, code};
        map->insert (pair);
    }
    if ( tree->getLeftChild () )
        fillLetterMap (map, tree->getLeftChild(), false, base, size + 1, false);
    if ( tree->getRightChild () )
        fillLetterMap (map, tree->getRightChild(), false, base, size + 1, true);

}

/** void decode (Node<Entry>* tree, const char* text, char* output, int limit)
 *
 * This function decodes compressed text
 *
 * @param Node<Entry>* tree - Huffman tree
 * @param const char* text - compressed text
 * @param char* output - output buffer
 * @param int limit - how many bits to decode
 * 
 */
void decode (Node<Entry>* tree, const char* text, char* output, int limit)
{
    int size = limit;
    Node<Entry>* currentTree = tree;
    unsigned int written = 0;
    for (int i = 0; i < limit; i++)
    {
        if ( currentTree->isTerminal () )
        {
            output[written] = currentTree->getValue()->letter;
            written++;
            currentTree = tree;
        }
        if ( getBit (text, i) )
            currentTree = currentTree->getRightChild ();
        else
            currentTree = currentTree->getLeftChild ();
    }
}

/** int code (Node<Entry>* tree, const char* text, char* output, int limit)
 *
 * This function compresses text
 * 
 * @param Node<Entry>* tree - the root node of Huffman tree
 * @param const char* text - original text
 * @param char* output - output buffer to write result in
 * @param int limit - the maximal size of output buffer
 *
 * @return amount of bits that was written
 *
 */
int code (Node<Entry>* tree, const char* text, char* output, int limit)
{
    char base[4] = "";
    std::map<char, Code> map;
    fillLetterMap (&map, tree, true, base, 0, true);
    int bitIndex = 0;
    int readIndex = 0;
    while ( text[readIndex] )
    {
        Code code = map[text[readIndex]];
        for (int i = 0; i < code.bits; i++)
        {
            setBit (output, bitIndex + i, getBit(code.code, i));
        }
        bitIndex += code.bits;
        readIndex++;
    }
    return bitIndex + 1;
}

/** void debugPrintTree (Node<Entry>* node, char legacy[10], int size, bool right)
 *
 * DEBUGGING FUNCTION
 *
 */
void debugPrintTree (Node<Entry>* node, char legacy[10], int size, bool right)
{
    char base[10] = "";
    memcpy (base, legacy, 10);
    if ( size >= 9 )
        return;
    if ( right )
        base[size] = '1';
    else
        base[size] = '0';
    base[size+1] = 0;
    size++;
    if ( node->getValue()->letter != 0 )
        printf ("\n[%c]:%s",node->getValue()->letter, base);
    if ( node->getLeftChild () )
        debugPrintTree (node->getLeftChild(), base, size, false);
    if ( node->getRightChild () )
        debugPrintTree (node->getRightChild(), base, size, true);
}
